package cn.whdream.datastructure.tree;
/**
 * 
 * @author admin
 *  二叉树 前序中顺序后序
 */
public class BinaryTreeDemo {
	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		//创建需要的结点
		HeroNode root = new HeroNode(1, "宋江");
		HeroNode node2 = new HeroNode(2, "吴用");
		HeroNode node3 = new HeroNode(3, "卢俊义");
		HeroNode node4 = new HeroNode(4, "林冲");
		HeroNode node5 = new HeroNode(5, "关胜");
		
		//说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
		root.setLeft(node2);
		root.setRight(node3);
		node3.setRight(node4);
		node3.setLeft(node5);
		binaryTree.setRoot(root);
		
		//测试
//		System.out.println("前序遍历"); // 1,2,3,5,4
//		binaryTree.preOrder();
		
//		System.out.println("前序结果:"+binaryTree.preOrderSearch(5));
//		System.out.println("中序结果:"+binaryTree.infixOrderSearch(5));
//		System.out.println("后序结果:"+binaryTree.postOrderSearch(5));
		//测试 
//		System.out.println("中序遍历");
//		binaryTree.infixOrder(); // 2,1,5,3,4
//		
//		System.out.println("后序遍历");
//		binaryTree.postOrder(); // 2,5,4,3,1
		
		System.out.println("删除节点");
		binaryTree.delNode(3);
		binaryTree.preOrder();
	}
	private static class BinaryTree {
		private HeroNode root;
		
		public void setRoot(HeroNode root) {
			this.root = root;
		}
		
		//删除结点
		public void delNode(int no) {
			if(root != null) {
				//如果只有一个root结点, 这里立即判断root是不是就是要删除结点
				if(root.no == no) {
					root = null;
				} else {
					//递归删除
					root.delNode(no);
				}
			}else{
				System.out.println("空树，不能删除~");
			}
		}
		//前序遍历
		public void preOrder() {
			if(this.root != null) {
				this.root.preOrder();
			}else {
				System.out.println("二叉树为空，无法遍历");
			}
		}
		
		//中序遍历
		public void infixOrder() {
			if(this.root != null) {
				this.root.infixOrder();
			}else {
				System.out.println("二叉树为空，无法遍历");
			}
		}
		//后序遍历
		public void postOrder() {
			if(this.root != null) {
				this.root.postOrder();
			}else {
				System.out.println("二叉树为空，无法遍历");
			}
		}
		
		//前序遍历
		public HeroNode preOrderSearch(int no) {
			if(root != null) {
				return root.preOrderSearch(no);
			} else {
				return null;
			}
		}
		//中序遍历
		public HeroNode infixOrderSearch(int no) {
			if(root != null) {
				return root.infixOrderSearch(no);
			}else {
				return null;
			}
		}
		//后序遍历
		public HeroNode postOrderSearch(int no) {
			if(root != null) {
				return this.root.postOrderSearch(no);
			}else {
				return null;
			}
		}
	}
	/**
	 * 前 1 2 3 5 4
	 * 中 2 1 5 3 4
	 * 后 2 5 4 3 1   
	 * @author admin
	 * 
	 */
	private static class HeroNode{
		private String name;
		private int no;
		private HeroNode left;
		private HeroNode right;
		

		public HeroNode( int no,String name) {
			super();
			this.name = name;
			this.no = no;
		}
		/**
		 * 	叶子结点 直接删除
		 *     非叶子结点，直接删除该子数
		 * @param no2 指定的结点号
		 */
		public HeroNode delNode(int no2) {
			HeroNode result;
			if(this.left != null && this.left.no == no2) {
				result = this.left;
				this.left = null;
				return result;
			}
			if(this.right != null && this.right.no == no2) {
				result = this.right;
				this.right = null;
				return result;
			}
			if (this.left != null) {
				return left.delNode(no2);
			}
			if (this.right != null) {
				return right.delNode(no2);
			}
			return null;
		}

		public HeroNode postOrderSearch(int no2) {
			System.out.println("进入后序遍历");
			if (left != null) {
				if (left.postOrderSearch(no2) != null) {
					return left.postOrderSearch(no2);
				}
			}
			
			if (right != null) {
				if (right.postOrderSearch(no2) != null) {
					return right.postOrderSearch(no2);
				}
			}
			
			if (this.no == no2) {
				return this;
			}else {
				return null;
			}
			
		}

		public HeroNode infixOrderSearch(int no2) {
			System.out.println("进入中序遍历");
			if (left != null) {
				if (left.infixOrderSearch(no2) != null) {
					return left.infixOrderSearch(no2);
				}
			}
			if (this.no == no2) {
				return this;
			}
			if (right != null) {
				if (right.infixOrderSearch(no2) != null) {
					return right.infixOrderSearch(no2);
				}
			}
			return null;
		}

		public HeroNode preOrderSearch(int no2) {
			System.out.println("进入前序遍历");
			if (this.no == no2) {
				return this;
			}
			if (left != null) {
				if (left.preOrderSearch(no2) != null) {
					return left.preOrderSearch(no2);
				}
			}
			if (right != null) {
				if (right.preOrderSearch(no2) != null) {
					return right.preOrderSearch(no2);
				}
			}
			return null;
		}

		@Override
		public String toString() {
			return "HeroNode [name=" + name + ", no=" + no + "]";
		}
		
		public void preOrder() {
			System.out.println(this);
			if (left != null) {
				left.preOrder();
			}
			if (right != null) {
				right.preOrder();
			}
		}
		
		public void infixOrder() {
			if (left != null) {
				left.infixOrder();
			}
			System.out.println(this);
			if (right != null) {
				right.infixOrder();
			}
		}
		
		public void postOrder() {
			if (left != null) {
				left.postOrder();
			}
			
			if (right != null) {
				right.postOrder();
			}
			
			System.out.println(this);
		}
		
		public HeroNode getLeft() {
			return left;
		}
		public void setLeft(HeroNode left) {
			this.left = left;
		}
		public HeroNode getRight() {
			return right;
		}
		public void setRight(HeroNode right) {
			this.right = right;
		}
	}
}
